COMMENT ⊗   VALID 00013 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	.DEVICE XGP
C00005 00003	5↓_ABSTRACT_↓*
C00007 00004	5↓_1. Motivation_↓*
C00015 00005	5↓_2. External Behavior of a BEING_↓*
C00022 00006	5↓_3. Internal Structure of a BEING_↓*
C00035 00007	5↓_4. A Universal Set of BEING Parts_↓*
C00042 00008	5↓_5. What Happens When a BEING Gains Control_↓*
C00047 00009	5↓_6. Character of BEING Interactions_↓*
C00053 00010	5↓_7. Theory of Pure BEINGs Systems_↓*
C00062 00011	5↓_8. Experimental System_↓*
C00083 00012	5↓_9. Conclusions_↓*
C00090 00013	5↓_10. References_↓*
C00093 ENDMK
C⊗;
.DEVICE XGP

.FONT 1 "BASL30.FNT[IJ,DBL]"
.FONT 2 "BASB30"
.FONT 3 "NGR25"
.FONT 4  "BASI30.FNT[IJ,DBL]"
.FONT 5  "NGR40"
.FONT 6  "FIX25"
.TURN ON "↓_π{"
.TURN ON "⊗" FOR "%"
.PAGE FRAME 41 HIGH 89 WIDE
.AREA TEXT LINES 1 TO 41
.!XGPLFTMAR←120
.SPACING 70 MILLS
.PREFACE 180 MILLS
.NOFILL
.PAGE FRAME 41 HIGH 89 WIDE
.AREA TEXT LINES 1 TO 41
.PREFACE 45 MILLS
.FILL
.NEXT PAGE
.MACRO B ⊂ BEGIN VERBATIM GROUP ⊃
.MACRO BB ⊂ BEGIN NOFILL SKIP 2 SELECT 3 INDENT 0 GROUP ⊃
.MACRO E ⊂ APART END ⊃
.TABBREAK
.SELECT 1
.COMPACT
.BEGIN CENTER
⊗5  BEINGS:  KNOWLEDGE AS INTERACTING EXPERTS⊗*

⊗2Douglas B. Lenat
Stanford Artificial Intelligence Laboratory
Stanford, California⊗*

⊗5↓_ABSTRACT_↓⊗*

.END

.INDENT 6

	Knowledge, including that of control, may be organized  as  a
community  of  interacting  modules  (e.g., ACTORS). Each module is granted
a complex structure, to simulate a particular expert in some small domain.
By constraining   that  this  structure  be  standard  over  the  entire
community, some advantages  of  a  uniform  formalism might be preserved.
The most natural task domain is shown to be automatic programming;
an  experimental  system  was  partially
implemented  for  this. It has managed to synthesize 
a few inductive
inference  LISP  programs, nonformally,  from  specific  restricted
dialogues.   This  research  clarified  some difficulties of using
structured modular systems and of automatic programming.

.B

.E
.ONCE CENTER
⊗5↓_1. Motivation_↓⊗*

Consider an interdisciplinary enterprise, attempted by a community of human
experts who are specialists in -- and only in -- their own fields.  What modes of 
interactions will be productive?  The dominant paradigm might well settle into
⊗4questioning and answering⊗* each other.
When a topic is being considered, one or two
experts would recognize it and demand the floor. In the course of their exposition
they might need to call on other specialists. This might be by name, by specialty,
or simply by posing a new sub-question and hoping someone could recognize his own
relevance and volunteer a suggestion.  Such transfers would be more common at
the beginning, when the task is (by assumption) too general for any one member to
comprehend.  As the questions focus on more specific issues, single individuals
will be able to supply complete solutions.
If the task is to construct something, then the
activities of the experts should not be strictly verbal.  Often, one will 
recognize his relevance to the current situation and ask to ⊗4do⊗* something:
create a new thing, modify one which already exists.

What would it mean to ⊗4simulate⊗* the above activity?  Imagine several little 
programs, each one corresponding to a different expert. What must each program,
called a ⊗4BEING⊗*, be capable of?  It must possess a corpus of specific facts and
strategies for its designated speciality. It must interact via questioning and
answering other BEINGs, including the ability to recognize when it is relevant.
BEINGs must also be able to set up and to alter structures representing 
what the humans produce.

To be more concrete, suppose the humans' task is to design and code a large
computer program: a concept formation system[2]. Some experts will be scientific
programmers, non-programming psychologists,
system hackers, management personnel, and so on.
What happens in the ensuing session?  When an expert participates, he will
either be aiding a colleague in some difficulty
or else transferring a tiny bit of his expertise into a programmed function
which can do something.  The final code reflects the members' knowledge.
One way the session might proceed is for the specialists to actually ⊗4do⊗*
the concept formation task. As they become familiar with what part of their own
expertise is being called upon, and in what ways, they can begin to isolate it.
When it is clear precisely what each is doing, they can take their extracted
bits of knowledge,
organize them,
formalize them, and program them.  A conscious
effort along these lines was made in [7], where experts gradually replaced
themselves by programs.  Instead of discussing how to write a speech program,
they ⊗4did⊗* speech recognition, until each one could introspect sufficiently
into his own activities to formalize them.

How could BEINGs do this? There would be some little program containing information
(much of it never to be used) about ⊗3CONCEPT-FORMATION⊗*, another BEING who knows
how to manage a group to
⊗3WRITE-PROGRAMS⊗*, and many lower-level specialists, for example 
⊗3OBTAIN-USABLE-INFORMATION, TEST, MODIFY-DATA-STRUCTURE, UNTIL-LOOP, 
VISUAL-PERCEPTION, AVOID-CONTRADICTION, PROPOSE-PLAUSIBLE-NAME⊗*.
Some chairman might be necessary (a global monitor), or merely universally
accepted means of communicating, of gaining the floor, and of resolving disputes.
The project sponsor might be passive, submitting a single specification order for
the program, or active, participating in the work as a (somewhat priveleged) member
of the team. This individual is the one who wants the final product, hence will be
called the ⊗4user⊗*. 
Although specialists, the BEINGs would contain far too much information, far too
inefficiently represented, to be able to say "we ourselves are the desired program!"
They would have to discuss, and perhaps carry out, the concept formation task. They
would write specialized versions of themselves, programs which could do exactly what
the BEINGs did to carry out the task, no more nor less. Some BEINGs 
(e.g., ⊗3TEST⊗*) may have several
specialized, streamlined fractions of themselves in the final program. BEINGs which
only aided other BEINGs (e.g., ⊗3PROPOSE-PLAUSIBLE-NAME⊗*)
will not have ⊗4any⊗* correlates in the ultimate
synthesized code.

A system was designed and partially implemented to study this process. A concept
formation program similar to [6] was actually synthesized, but the user must 
come up with certain specific answers to some of the BEINGs' critical queries.
A grammatical inference program and a  simple property list maintenance routine
were also generated, but similar dialogue problems plagued these efforts.
Before describing this community of BEINGs, individual BEINGs are vivisected.

.B

.E
.ONCE CENTER
⊗5↓_2. External Behavior of a BEING_↓⊗*

⊗3WRITE-PROGRAM⊗* is a high-level, programming-knowledge BEING. It can answer
several questions relevant to managing code production, 
and in the course of answering it
calls on other BEINGs when it feels deficient. 
Here are some of the things which another BEING -- or the user -- might ask
⊗3WRITE-PROGRAM⊗*, and its replies:

.BEGIN NOFILL INDENT 0

Can you recognize this phrase: "Write a program which does frob gyrnation" ?
⊗3  If anyone can recognize the act of "frob gyrnation", then I will handle it.⊗*

What argument(s) do you require?
⊗3  One argument, binding (by λ) the variable "task". Two local variables are used.⊗*

What do you do?
⊗3  I write a program which does <value of task goes here>.⊗*

Why?
⊗3  Fundamental drive to serve; code must be written to do <task>; ask <whoever called me>.⊗*

When should you take control?
⊗3  If <task> can already be done in some way, I probably shouldn't speak up.
  If the user is aware that I want to go, and does not voice objection, I will go.
  If there is any new but unassimilated info around, it should be scrutinized first.⊗*

What happens when you are in control?
⊗3  A program for <task> gets initialized.
  Until it is completed, I repeatedly pass control among four BEINGs
    (OBTAIN-USABLE-INFO, USE-INFO, FILL-IN-UNDEFINED-PIECE, CLARIFY-IMPROBABLE-PIECE)
    They, not I, decide which of them should be in control at each instant.
  It is complete when code for <task> exists, there are no coding-warnings, no new info,
    no undefined pieces of code, no deferred decisions left unresolved.
  When complete, I assert this fact, call on SUPPORT-AND-DUMP to optimize the program
    and store it on a new disk file, and relinquish control to whoever wants it most.⊗*

What must be made true before you start all this?
⊗3  Some BEING must make the user aware that I am about to write a program for <task>.
  <task> must have a proper name <task-name> (some BEING must bring this effect about).⊗*

What must be attempted after you are finished?
⊗3  Try to make the user aware that I have written the program <task-name> for <task>⊗*

What should you be on the watch for while you have the floor?
⊗3  Activate demons for deferral and reinvestigation of decisions.⊗*

What are the main effects of your having (successfully) finished your job?
⊗3  The user, and any BEING, can do <task>; code has been written for <task>.⊗*

How complex/costly are you?
⊗3  The difficulty to call is 0.3  +  0.7 * (estimated difficulty of <task>)
  There is a 0.9 chance that I will be called recursively by myself or a descendant.
  There is a 0.7 chance of my success, in general, if I actually gain control.
  I will use a disproportionate share of time and space if I am called.
  There is generally no reason to absolutely inhibit me.⊗*

.END

The fractional numbers in the last answer represent the author's guesses, on a
scale of zero to one. 
One question which can't be answered by ⊗3WRITE-PROGRAM⊗* is "How do you write a
specialized version of yourself?"   Many
BEINGs ⊗4do⊗* have this ability, and a brief example is now given.  
⊗3PARTITION-A-DOMAIN⊗* contains knowledge relevant to many kinds of inductive
inference programs, including concept formation.
Here are a few of its answers:

.NOFILL

What is your basic idea, what do you do?
⊗3  Divide a space of elements into named classes, by gradually building up a partition.⊗*
.SKIP TO COLUMN 1
What happens when you are in control?
⊗3  Repeatedly: accept an input;
	if it is a <element,class-name> pair, merely add it to the current partition;
	if it has element but no name, try to guess its name, then check with the user;
	if it has name but no element description, guess what element it might be, and check;
	if I had to guess, some modification of my guessing strategies might be done.⊗*

Instead of acting, how can you write a streamlined version of yourself?
⊗3  If can guarantee that partition is total, every element must be tied to some class-name.
  If can guarantee that partition is strict, no element can belong to >1 class ever.
  Only some of the three types of inputs might ever occur, might need to be differentiated.⊗*

What BEINGs should be considered if you fail?
  ⊗3DISCRETIZE is an alternative; CREATE-FUNCTION is a generalization.⊗*

.FILL

.ONCE CENTER
⊗5↓_3. Internal Structure of a BEING_↓⊗*

Each BEING is composed of a couple dozen parts, each of which is the name
of a question and a little program for how this BEING should answer it. 
This answering program may itself pose questions (to other parts of the
same BEING, to parts of other BEINGs, to the user), assert propositions,
create and modify structures (including demons and parts of BEINGs).

Several design questions arise: what parts are filled in for each BEING,
how does any part know what questions it may ask each BEING, how do the values
of the parts get determined,...?
Before discussing these design aspects of an interacting community, the actual
parts of a particular BEING in the experimental system will be presented. Consider 
⊗3OBTAIN-USABLE-INFORMATION⊗*, a BEING which is independent of task domain.
Below is listed, for each part, its abbreviated name, a fuller English question, the
value stored, and a brief explanation.

.BB
⊗2WHAT⊗*	What do you do?     	 (OBTAIN SOME INFORMATION WHICH CAN BE USED) 
⊗2WHY⊗*		 Why?     (PUP HAS NO MORE INFORMATION THAT IT CAN USE TO PROGRESS) 
⊗2HOW⊗*     	 How?     (OBTAIN NEW FACTS ABOUT OLD INFORMATION, OR OBTAIN TOTALLY NEW INFO)
.E
These three parts are primarily for the user's benerfit. In the current
case, they don't even have any uninstantiated parts.  If the user asks one
of these questions when this BEING is in control, then the appropriate
answer can simply be typed out.

.BB
⊗2IDEN⊗*	   Can you recognize this phrase: "Find out more about frob gyrnation"?
((if you see:  (OBTAIN-USABLE-INFORMATION any1) 
				then return:(OBTAIN-USABLE-INFORMATION (TRANSLATE any1)))
 (if you see:  (FIND OUT MORE ABOUT any1)    
				then return:(OBTAIN-USABLE-INFORMATION any1)))
.E
.SKIP TO COLUMN 1

The phrase matches the second template. ⊗3OBTAIN-USABLE-INFORMATION⊗* is given
control, with "frob gyrnation" as its argument. If it does not fail, the
value it returns is taken to be the translation of the original phrase.
Each BEING is given the duty of recognizing and processing English phrases
related to him.  In practice, only a few simple phrase templates were
needed for each BEING; ⊗3OBTAIN-USABLE-INFORMATION⊗* only used two patterns.
All the IDEN parts are collected together into one table.  When a form
⊗4F⊗* must be translated, the ⊗3TRANSLATE⊗* BEING takes control and (by
searching this table) asks "who can recognize ⊗4F⊗*?"  Each IDEN part
runs a little program (typically a pattern-match), then replies either
NO, or else provides a little program whose value should be the translation
of ⊗4F⊗*.  If there is more than one responder, a global choice BEING,
⊗3CHOOSE-FROM⊗*, selects the winner.  Often
the program which is
returned calls ⊗3TRANSLATE⊗* recursively on some parts
of ⊗4F⊗*.

.BB
⊗2EXPLICIT-ARGS⊗*    	What argument(s) do you take?  		( U )
⊗2NLAMBDA⊗*		    Which are quoted, not evaluated?         NIL
⊗2IMPLICIT-ARGS⊗*	What local variables are needed?	 NIL
.E
The argument to this BEING is never operated upon, hence there is no need to
understand anything about it.  It is simply passed to BEINGs called by
⊗3OBTAIN-USABLE-INFORMATION⊗*.

.BB
⊗2WHEN⊗*	When should you take control (justify your answer)?
((if T then add in -10 because (THIS IS EXPONENTIALLY-GROWING, GENERALLY UNDESIRABLE))
 (if NEW-INFO-LIST then add in  (PLUS  100  (LENGTH  NEW-INFO-LIST))
       	because (WE SHOULD WORK ON UNASSIMILATED NEW  INFORMATION IF THERE IS ANY)))
.E
The WHEN part of a BEING is a collection of triples: if <predicate> then
<value> because <reason>.  If the <predicate> evaluates to non-null, then
the <value> program is executed. It returns a number, which is then added
together with the other factors' numbers to produce a rough estimate of
how a propos this BEING is to take control right now.  The <reason>
evaluates to an English phrase, for the benefit of inquisitive users.
This linear scheme is undesirable but (sigh) adequate. The first factor
here says to always add in the number -10; the second says
if there is some new information sitting around unexploited, to add in 100
plus the number of such pieces.
These factors and their weights, like the contents of all the parts
of all the BEINGs initially in the experimental system, 
were decided upon and inserted by
hand.

.BB
⊗2META-CODE⊗*   	What happens when you are in control?
(DO
     (CHOOSE-FROM ((GET-NEW-INFORMATION U)
	    	         (TRANSLATE U)
	                 (ANALYZE-IMPLICATIONS U)
			 (EXTRACT-RELEVANT-SUBSET U)))
  BECAUSE
      (WE CAN ONLY TRY TO OBTAIN USABLE INFORMATION IN ONE WAY AT A TIME))
.E
.SKIP TO COLUMN 1
Once it gains control, the BEING chooses from  the  following  four
alternatives,    each    of    which    is    itself     a     BEING:
Get-Brand-New-Information  (in  English,  from  the  user), Translate
something    (transform     from     English     to     BEING-calls),
Analyze-The-Implications  (of some existing, translated information),
Extract-a-Relevant-Subset   (of   the   existing   information)    to
concentrate upon.

.BB
⊗2MAIN-EFFECTS⊗*      Can you cause this to occur: "Usable information exists"?
((to get (NEW INFORMATION any1)       do (OBTAIN-USABLE-INFORMATION any1))
 (to get (USABLE INFORMATION any1)   do (OBTAIN-USABLE-INFORMATION any1)))
.E
The EFFECTS parts of each BEING are collected  into
one  table  to  facilitate  asking all BEINGs simultaneously "Can you
cause effect ⊗4X⊗* to occur?" Each EFFECTS part examines ⊗4X⊗* and  the  world,  and
either  replies ⊗4No⊗*, or else returns a little program (involving calls
and constants) which  should  produce  the  effect when it is run.
This program generally will involve a call to the BEING
itself. ⊗3OBTAIN-USABLE-INFORMATION⊗* shows that it should be called to acheive
the existence of new or usable information.

.BB
⊗2AFFECTS⊗*     	What other BEINGs might you call on directly?
((CHOOSE-FROM is called)
 (some BEING who can cause (AWARE USER (ABOUT TO OBTAIN USABLE INFO)) is called)
 (GET-NEW-INFORMATION possibly is called)
 (TRANSLATE possibly is called)
 (ANALYZE-IMPLICATIONS possibly is called)
 (EXTRACT-RELEVANT-SUBSET possibly is called) )
.E
This part is clear; ⊗3CHOOSE-FROM⊗* is definitely going to be called on,
another one called on is specified only by its effects, and each of
the other four BEINGs mentioned might be called and might not be.

.BB
⊗2COMPLEXITY-VECTOR⊗*   	How costly are you?		(.5 .5 .9 .5 .1) 
.E
The first component says that ⊗3OBTAIN-USABLE-INFORMATION⊗* is of average
difficulty to call. Next, there exists a .5 chance that some descendant
will call it again. The third component indicates that this activity almost
always succeeds. The time/space used in allowing this BEING to try
is typical. Finally, there is no good reason for inhibiting
it ever.  In general, each component can be a ⊗4program⊗*,
not just a constant.

.BB
⊗2GENERALIZATIONS⊗*      What BEINGs are more general than you?  
(WRITE-PROGRAM SERVE-THE-USER)
⊗2ALTERNATIVES⊗*          What BEINGs are similar to you, alternatives in case you fail?
(USE-INFORMATION FIX-INCORRECT-PIECE OPTIMIZE FILL-IN-UNDEFINED SECTION)
.E
These list things to try if this BEING fails in its mission. The 
alternatives should generally be tried before the more general BEINGs.

.SKIP TO COLUMN 1
.ONCE CENTER
⊗5↓_4. A Universal Set of BEING Parts_↓⊗*

Having decided to represent knowledge as interacting modules, communicating via
questioning, one must now examine how each BEING knows what questions it can ask
each other BEING.  ACTORS [3] solves this problem by ⊗4handshaking⊗*; each module
must be compatible with all the others it is ever going to interact with. While
this makes the representation of each ACTOR efficient, it is conceptually difficult
to add new ACTORS to the community without knowing a great deal about who is there
already. A universal set of BEING parts 
(= ACTOR message formats) might be developed,
in the sense that each module must have each part filled in. The danger here is
the huge number of parts which might be necessary, and the irrelevance of most of
them to any given BEING. Perhaps by restricting the task that the pool of BEINGs is
supposed to do, the number of parts necessary might drop to a reasonable figure.

An experimental pool of a hundred BEINGs was designed and 
partially implemented, to test both the hypothesis of a universal set of parts
and the feasiability of BEINGs in general.  The system, named PUP6, was aimed at
synthesizing LISP programs from restricted discussions within itself and
with the user. In particular, 
the community's task was to generate a particular concept 
formation program, communicating with the user in a miniscule subset of English.
So a fixed set of BEING parts need only be relevant to
writing a small subclass of inductive inference LISP programs, and to handling
simple dialogue. Such a set was actually chosen,
consisting of 29 different parts. 

The specific parts decided upon are relevant to  the
epistemology of programming.  The universal set is listed below; recall that
each part of a BEING corresponds to a question 
which is answered by that part's value.
The percentage of the experimental pool  of BEINGs
which actually needed each part is also noted.

.BEGIN NOFILL FLUSH LEFT SELECT 3

⊗2WHAT⊗* 82%  A brief summary of the global purpose, a template for an English phrase.
⊗2WHY⊗* 77%  A justification of the BEING's existence, partly by the one who called it.
⊗2HOW⊗* 72%  A summary of the methods the BEING intends to employ. Global strategies.
⊗2IDEN⊗* 54%  How this BEING is referenced in English phrases? Implemented as productions.
⊗2WHEN⊗* 19%  Why this BEING should be given control now. The sum of weighted factors.
⊗2ARGS⊗* 63%  Number of arguments, which are optional, names of any local variables.
⊗2ARG-CHECK⊗* 81%  Predicates which examine each argument for suitability.
⊗2EVAL-ARGS⊗*  4%  Which arguments are to be evaluated, and which quoted.
⊗2REQUISITES⊗* 10%  If this BEING is actually chosen, what must be made true prior to (pre)
	during (co), and after (post) execution.  Work to make these true (unlike ARG-CHECK).
⊗2DEMONS⊗* 7%  Set of demons to be kept active while the BEING is in control.
⊗2INHIBIT-DEMONS⊗*  5%  A lock/unlock mechanism, useful when handling demonic interrupts.
⊗2EFFECTS⊗* 27%  What will probably be true after this BEING is through. What it achieves.
⊗2RESULTS⊗* 15%  How many values this returns. What domain each is in. Side effects.
⊗2META-CODE⊗* 70%  The body of the executable code, but with uninstantiated subparts.
⊗2COMMENTS⊗* 16%  Hints for filling in undefined sections of other BEING parts.
⊗2STRUCTURE⊗* 4% Viewing this BEING as a data structure, the operations doable to it.
⊗2AFFECTS⊗* 14%  Other BEINGs which might be called by this BEING, and why.
⊗2COMPLEXITY⊗* 92%  A vector of utility measures, including probable ease of calling,
	success, (calling)* itself, time/space cost, efficiency of its output results.
⊗2GENERALIZATIONS⊗* 27%  Some other BEINGs, encompassing this one.
.SKIP TO COLUMN 1
⊗2ALTERNATIVES⊗* 16%  Some equivalent BEINGs (to try if this one fails).
⊗2SPECIALIZATIONS⊗* 40%  How to write a streamlined, special-case version of this BEING.
⊗2ENCODABLE⊗* 9%  How to order the evaluation of the other parts for self-streamlining.
⊗2FORM-CHANGING⊗* 1%  How to perform radical alterations of parts (in special cases).

.END

.ONCE CENTER
⊗5↓_5. What Happens When a BEING Gains Control_↓⊗*

The commitment to a universal set of BEING parts is inefficient in some ways
(each BEING ⊗4needed⊗* only a third of all the parts) but allows for some
simplifications. What parts should be evaluated, and in what order, when a 
BEING gains control? This decision depends primarily on the ⊗4types⊗* of parts
present in the BEING, not on their ⊗4values⊗*.  But every BEING has the same
set of parts, so one single algorithm can assemble any BEING into an executable
LISP function. Moreover, this assemby can be done when the system is first
loaded (or when a new BEING is first created), and need only be redone for a
BEING when the values of its parts change. Such changes are rare: experts are
not often open-minded. 

When a BEING ⊗4B⊗* first gains control, its ⊗3EXPLICIT-ARGS⊗* are bound. The
⊗3IMPLICIT-ARGS⊗* are initialized, the name ⊗4B⊗* is pushed onto the BEING
control stack, and any newly-activated ⊗3DEMONS⊗* are so tagged. The
BEING who called ⊗4B⊗* should have explained his reasons by assigning
the variable ⊗3BECAUSE⊗* to some phrase.  This reason is now stored as a
special sub-part of the WHY part of ⊗4B⊗*.
⊗3BECAUSE⊗* is rebound periodically in the META-CODE and COMMENTS parts, to
keep current the explanation of each call that ⊗4B⊗* makes. 
Each ⊗3ARG-CHECK⊗* predicate is evaluated. If none returns NIL, the
⊗3PRE-REQUISITES⊗* are examined. Effort is expended to make them true, if they
are currently not satisfied. Each ⊗3COMMENT⊗* is evaluated, then the
⊗3CO-REQUISITES, META-CODE⊗*, and the current demons
are executed in pseudo-parallel.  Each ⊗3POST-REQUISITE⊗* is then examined, and
an effort made to satisfy it.  The newly-activated demons are exorcized, the
BEING stack is popped, and the value computed by the ⊗3META-CODE⊗* is returned.

Some heuristics were devised to take advantage of the fact that the BEINGs often
didn't need many of the standard parts. For example, ⊗3OBTAIN-USABLE-INFORMATION⊗*
has no new demons or co-requisites, so no parallel processing need be simulated.
No results are explicitly produced, so the value returned by the ⊗3META-CODE⊗* is
not saved and later returned.
Here is the way that BEING actually appeared after assembly;
contrast this with the values of
its parts, as presented in Section 3.
.BEGIN NOFILL SELECT 3 

(OBTAIN-USABLE-INFORMATION
  (LAMBDA  (U)
      (AND
	(PUSH  OBTAIN-USABLE-INFORMATION  BEING-STACK)
        (PUT-APPEND  OBTAIN-USABLE-INFORMATION  WHY  BECAUSE)
	(EVERY  CURRENT-DEMONS  APPLY*)
	(SETQQ BECAUSE (WE CAN ONLY TRY TO OBTAIN USABLE INFO IN ONE WAY AT A TIME))
	(CHOOSE-FROM   
		 (GET-NEW-INFORMATION U)
		 (TRANSLATE U)
		 (ANALYZE-IMPLICATIONS U)
		 (EXTRACT-RELEVANT-SUBSET U))
        (POP  BEING-STACK))))
.END
.SKIP TO COLUMN 1
.ONCE CENTER
⊗5↓_6. Character of BEING Interactions_↓⊗*

To demonstate the flavor of BEINGs actively doing something, an
excerpt will be presented from a dialogue between a human user and PUP6, the
experimental pool of BEINGs. The ⊗4external⊗* character involves considering all
of PUP6 as one entity, not distinguishing which BEING asked the user something,
not observing the discussion taking place strictly among BEINGs. After the
example is a fuller discussion of what went on ⊗4internally⊗*.
The intent of the user in this dialogue is to encode the concept formation
program. Here is the initial and final few lines of that 300-page dialogue:

.BEGIN NOFILL

PUP: I want any task.
USER: Write a program which does concept formation
PUP: I am about to write a program for ⊗3specialized CONCEPT-FORMATION⊗*. 
PUP: Give me a proper name for this program. (I suggest CF or CONCEPT)
USER: CF
PUP: Must CF mimic different human subjects? (respond YES, NO, ?, or DETAILS)
USER: NO
PUP: I am temporarily replacing the task "⊗3specialized form of CONCEPT-FORMATION⊗*"
 .		by "⊗3specialized form of PARTITION-A-DOMAIN⊗*".
 .
 .
PUP: I can no longer defer this NESTED decision (respond A, B, C, ?, DETAILS)
   A)  CF does classificatory concept formation
   B)  CF does comparative and classificatory concept formation
   C)  CF does metrical, comparative, and classificatory concept formation
USER: A
PUP: I have written the program CF for ⊗3specialized CONCEPT-FORMATION⊗*.
PUP: I want any task.

.END

The BEING initially in control is ⊗3SERVE-THE-USER⊗*. Its essential function is
to obtain new information until some of it is "obeyable", then obey it.

After the user's first order, the ⊗3WRITE-PROGRAM⊗* BEING gains control. He
asks for someone to type out his intentions, and ⊗3MESSAGE⊗* recognizes its
relevance and performs that service. Similarly, ⊗3GET-NAME⊗* temporarily
gains control to obtain a proper name. ⊗3WRITE-PROGRAM⊗* then enters its
REPEATEDLY loop (see Section 2). The user's command is usable information,
and the WHEN part of ⊗3USE-INFO⊗* has the highest value of the four choices.
When ⊗3USE-INFO⊗* is given control, it examines the SPECIALIZATIONS part of
⊗3CONCEPT-FORMATION⊗*. Eleven decisions are listed, whose answers
delimit the types of streamlining which are possible[2].  Each decision is
examined in turn. If it cannot be resolved, PUP6 tries to defer it.
For example, the type of concept formation may involve simple
partitioning, partitioning and ordering of the classes, or partitioning and
ordering and finding a metric on the space of classes of the partition. Since
all three choices involve partitioning, the decision may be deferred until after
code has been written for that subtask.  The rationale for deferral is that at a
later time, PUP6 might have enough new information to resolve the decision without
bothering the user. 
.SKIP TO COLUMN 1
Only one decision cannot be deferred: must the program simulate
various experimental subjects, or just one archtypical concept former? PUP6 has
no way of resolving this without asking the user, so it does.

After a CPU hour has elapsed, code for the type of partitioning desired has been
synthesized.  A demon then finds he must ask the user whether anything else
need be done by CF. When he replies negatively, ⊗3WRITE-PROGRAM⊗* finds itself
completely finished. Its POST-REQUISITES are satisfied by
⊗3MESSAGE⊗*, and it relinquishes
control to ⊗3SERVE-THE-USER⊗*.

.B

.E
.ONCE CENTER
⊗5↓_7. Theory of Pure BEINGs Systems_↓⊗*

Many constraints are placed on BEINGs as individuals and in groups. Here these
are collected. Hopefully, the ideas will be separated from the implementation
details, the prejudices from the plausible features.

It would be aesthetically pleasing to restrict all entities in the system to be
BEINGs. However, this would cause an infinite regress, 
as each part of each BEING would
have parts which had parts... To stop this, one can assert that certain
primitive constructs are allowed; for example, any part which can be expressed
as a few lines of LISP code involving no auxilliary function calls. 

Suppose there ⊗4were⊗* only BEINGs -- hence no functions -- allowed to exist.
In the case of an automatic programming task, the BEINGs would have to write new
BEINGs, not new LISP functions. The target program would thus itself be a
community of BEINGs. What effects would this have?  Many superfluous parts
would get filled in. What would be their significance?  They are organized
⊗4documentation⊗*, a standard system of comments tacked onto each BEING produced.

Which BEINGs would write the new BEINGs?  Looking back at our interdisciplinary
experts, we see that each expert is responsible for distilling his own essential
contribution, which is then encoded by a programmer.  Perhaps each BEING should be
able to direct construction of new, specialized BEINGs which relate to it. If
no BEING relates to a task, then it can't be coded; if several respond, they
should cooperate. This ability is in reality the SPECIALIZATIONS part proposed
earlier for each BEING. The BEING which actually does the creation
(⊗3MAKE-NEW-BEING⊗*) in the experimental system is almost trivial, getting very
precise instructions from other BEINGs.

Since the pool must communicate with the user, some BEINGs must translate
quasi-English phrases into calls on BEINGs.  Drawing again on our experts
analogy, we require that each BEING recognize his own relevance. So translation
is merely the act of asking the whole pool "Who can recognize this...", collecting
the responders, having ⊗4them⊗* decide who should take control, and letting the
winner do the translation.

A universal set of BEING parts should preserve some of the advantages of uniformity
(easy addition of knowledge to the system, easy inter-BEING communication). The
complex structure of a BEING should make complex behaviors feasable, including
dialogue flexibility as well as final products.  The ⊗4number⊗* of BEING parts is
a type of indicator of the balance between uniformity and structure in the
community. If it were ~1, there would be no structure (e.g., predicate calculus);
it it were the union of all the BEINGs' desires, ~1000, there would be no
uniformity (e.g., ACTORS). 

Automatic programming is distinguished as a task for BEINGs in the following sense.
Say a pool has been assigned task T.  They create new programs which simulate T.
If the original task had been to write a program which did T,  ⊗4there would be
no extra effort necessary⊗*. The new BEINGs would simply be dumped onto a file.

One bias is the rejection of debugging as a fundamental programming tool.
It is felt to be worth the extra effort to make the system's internal model of the
current partial target program ⊗4correct⊗*. Debugging demands detective work,
examing one's earlier efforts for flaws, for details which have been overlooked.
Ideally, an automatic programming system, including BEINGs, should not have to
ignore details.  At the least, they might defer them,
asserting a warning to this effect. It is felt that procrastination 
is quite valuable;
in PUP6, much effort
is spent deferring any unresolvable decision.
Undeferrable unresolvable decisions must cause a backtrack  point to be
reluctantly set up. Another prejudice is that most carelessness bugs can be 
eliminated by this deferral, feed-forward, and precise record-keeping. Humans
depend on their adaptability to compensate for limitations in their brain
hardware, but there is no need for an ⊗4automatic⊗* programming system to do so.

To clarify what BEINGs are and are not, they are contrasted with some other
ideas. FRAMES[4] are sufficiently amorphous to subsume BEINGs. In philosophy,
FRAMES are meant to model perception, and intentionally rely on implicit
default values; BEINGs intentionally avoid making decisions by default.
This same difference exists between HACKER and PUP6,
the experimental pool of BEINGS.
Since PUP6 writes structured programs, it appears similar to macro
expansion. Macro procedures expand mechanically:
⊗2expand(sequence   m↓1  m↓2) = (sequence  
expand(m↓1)  expand(m↓2)))⊗*. BEINGs could use
information gleaned during expansion of m↓1 to improve the way m↓2 was handled.

BEINGs linearly subsume many popular AI features;
the demonstration will be brief:
A ⊗4demon⊗* could be replaced by a BEING whose ARG-CHECK predicate was the
triggering predicate, whose WHEN part was high enough to ensure frequent
attention, and whose META-CODE part was the body of the demon. An ⊗4assertion⊗*
could be a BEING with only an IDEN part filled in; when it recognized its
relevance, a fully instantiated assertion is returned. A ⊗4function⊗* is
equivalent to a BEING with only a META-CODE, ARGS, and NLAMDA parts; one knows
almost nothing about it before executing it.
While theoretically clear, these subsumptions are very inefficient.
Replacing, e.g.,  an assertion by even a single (nondeterministic)
BEING call introduces an extra time factor proportional to the total
number of BEINGs in the system.

.B

.E
.ONCE CENTER
⊗5↓_8. Experimental System_↓⊗*

The first decision to be settled in constructing an actual pool of BEINGs is
what their task shall be.  The choice was automatic code generation
of simple inductive inference LISP programs,
from discussions with an ⊗4active⊗* user.
The universal set of BEING parts listed in Section 4 was 
constructed by introspection. 

What program would be the specific "target"?  A variant of Winston's
structural concept formation system was studied and simplified. A complete
dialogue was simulated by humans, supposedly between a user and a desirable
automatic programming system. Careful records were kept, and the "system"
wrote down his reasoning steps between successive outputs. A clean structured
program resulted, and the goal of the research became to elicit that program,
using virtually the same dialogue, from a pool of BEINGs.
The most important constraint was that the BEINGs actually go through states
corresponding to the human's reasoning steps.  
Two restrictions implicit here turned out to be serious: the abilities of the
actual user must coincide with those of the human who participated in the
protocol, and the order of and wording of the user's comments must closely
adhere to that single dialogue. These difficulties are central to any system
designed for wide usership, but were considered ignorable in the specific
automatic code generation task at hand.

At this stage, a rough initial set of about eighty BEINGs surfaced. Each one
had not much more than a name and a vague description of what it must do. The
dialogue was cycled through again, and the comments were replaced by a sketch of
which BEINGs would call which other ones, why, and the results of the call.
The necessary set of BEING parts  and the
constraints on each BEING thus grew. Occasionally an unexpected BEING
or BEING part had to be added to the design. Eventually, 17
inductive inference domain-specific BEINGs were called for, and another 70
which dealt with programming, organization, and communicating with the user.
As a result of this approach to system specification, each BEING had only those
parts specified which it actually would need in the ensuing dialogue.
Part of the difficulty with new dialogues stemmed from this minimal completion.

The system, PUP6, did eventually synthesize CF, 
the target concept formation program.
PUP6 was 200 pages of INTERLISP[5],  CF was 30 pages long (6 pages when
coded by hand during the simulation). This was generated in 60 cpu minutes
(compiled, PDP-10 TENEX). The dialogue consisted of 300K characters typed by
PUP6, and 4K by the user. The mean wait time between user input and
machine response was several cpu seconds; the longest delay was one cpu minute.

Two of the most significant questions for automatic proramming systems[1] are
how flexible the dialogue can be, and how different the generated programs can
be. Because of its genesis from a single protocol, the pool of BEINGs was simply
not capable of widely varied dialogues with the user.  It ⊗4was⊗* felt that
most of them could be useful in generating other programs, however. For this
reason, two additional target programs were specified.

All three synthesized programs are now discussed.
CF lacked an efficient heuristic graph-matcher
but is otherwise similar to [6]. Repeatedly, a scene 
(a set of objects and static structural relations
between them) is inputted. If no name is given, CF must guess one and then
check with the user. The guess is based on comparing the scene with internal
models of previously-named scenes, until one matches. After each input, the
models with the guessed and the correct names are modified. An incorrect
guess must not be made twice in a row on the same scene. For this, P. Gadwa
demonstrated that it suffices
to maintain three lists for each named model: 
those relations which must be present in
the observed scene for it to possibly have this name, those relations which
must never occur in any scene having this name, and those which may be
present or absent.

The target program GI is a grammatical inference program, which accepts
strings labelled LEGAL, ILLEGAL, or ??. In the latter case, GI must guess the
legality. Internally, potential sets of rules are maintained. Of the original
pool, 46 out of 70 "general" BEINGs were used in synthesizing both targets.
Three of the existing 17 
"domain-specific" BEINGs also were useful (those involving partitioning).
Four totally new BEINGs had to be added, related to formal grammars and rules.
While this number is small, the addition of ⊗4any⊗* new BEINGs demands that the
user be very familiar with all the format conventions of PUP6, all the
kluges, etc. The final GI program synthesized was 20 pages long; a hand-coded
version was one-fifth that size.

PL was the final target program attempted, a simple property list manipulator.
It repeatedly accepts requests from the user to insert, inspect, or delete
some record(s). Any unspecified fields are treated as don't-cares, so a simple
pattern-matcher had to be synthesized.
39 ⊗4general⊗* BEINGs were used in synthesizing ⊗4all three⊗* targets, but no
⊗4domain-specific⊗* BEINGs were common to synthesizing PL and any other program.
One general BEING and one domain-specific BEING had to be ⊗4added⊗* to PUP6
-- again, this is both encouragingly small yet far beyond the abilities of the
intended users.

Before delivering our verdict on this system, one further aspect is presented.
As proposed in Section 7, the BEINGs generate other BEINGs, not
just functions. This explains the huge increases in target code lengths. 
CF was a pool of 56 brand new BEINGs, GI 37, and PL 24. As
with PUP6, one can interrupt the target programs as they are running
and ask questions. Any BEING on the control stack will provide fully instantiated
answers to any of its 29 allowable queries; all other BEINGs will provide only
hypothetical answers. As an example, consider this excerpt between CF and the user.
Some liberty has been taken with the
English; e.g., the user really types ⊗4WHAT?⊗*, not ⊗4What are you doing?⊗*
PUP6 types in boldface, the user in italics.
.BEGIN NOFILL FLUSH LEFT SELECT 2

READY TO ACCEPT BRAND NEW SCENE:   ⊗4(??? (A B) (Block A) (Green B) (Touches A B))⊗*
NOT AN ARCH. NOT A TOWER. MIGHT BE A ROW.  MY GUESS IS ROW.
WHAT IS IT REALLY?		   ⊗4Nothing⊗*
TRANSFER FROM MAY TO MUST SETS OF ROW: (TOUCH A B)
READY TO ACCEPT BRAND NEW SCENE:
.END

Here is the ⊗4same⊗* excerpt, but with the user interrupting occasionally.
"⊗4U:⊗*"
signifies he has interrupted,
and "⊗4OK.⊗*" signifies he has told PUP6 "⊗4OK, go back to work now.⊗*"

.BEGIN NOFILL FLUSH LEFT SELECT 2

	⊗4U:  What are you doing?⊗*
PUP:  Divide a domain into subdomains, using specialized version of PARTITION-DOMAIN
  	⊗4How?⊗*
PUP:  By building up the partition gradually, by adding one <scene, name> pair. ⊗4OK.⊗*

READY TO ACCEPT BRAND NEW SCENE:   ⊗4(??? (A B) (Block A) (Green B) (Touches A B))⊗*

	⊗4U:  What are you doing?⊗*
PUP:  Break NAME piece off (??? (A B) (BLOCK A) (GREEN B) (TOUCHES A B)) to examine.
	⊗4What code is the current BEING going to execute?⊗*
PUP:  The meta-code of SOME-PART-OF↓1↓4 is (CAR arg1). Evals to ???. ⊗4OK.⊗*

NOT AN ARCH.
	⊗4U:  Why?⊗*
PUP: The ARCH MUST-relation (SUPPORTS A B) is contradicted in the SCENE. ⊗4OK.⊗*

NOT A TOWER. MIGHT BE A ROW.  MY GUESS IS ROW.
WHAT IS IT REALLY?		   ⊗4U:  Why are you asking?⊗*
PUP: PUP cannot resolve it, and must at this time, so PUP asks USER
	⊗4OK. What you wanted is:   Nothing⊗*

	⊗4U:  What are you doing?⊗*
PUP: Go through space of concept names, and make user aware of changes.
	⊗4What BEINGs might this affect?⊗*
PUP: MESSAGE is possibly called; some version of TEST is possibly called.  ⊗4OK.⊗*

TRANSFER FROM MAY TO MUST SETS OF ROW: (TOUCH A B)
READY TO ACCEPT BRAND NEW SCENE:


.END
.ONCE CENTER
⊗5↓_9. Conclusions_↓⊗*

What have we learned from this experimental study? The overall
feasability of BEINGs was demonstrated, but the difficulties of communicating
with the user made the system almost impossible to work with. The set of
questions the user was expected to want to ask is the same as the set that one
BEING can ask another: the BEING parts. When the "nice" user interrupts, his
questions are translated trivially into a simple retrieval. Real users are
seldom nice; the BEINGs generally misunderstood what users asked.

To modify PUP6 to synthesize a new program, it is necessary to add a few
general BEINGs, generalize a few existing BEINGs' parts, and add several 
BEINGs specific to the new program's domain. If even one new BEING must be added,
the task becomes very complex. Also, the dialogue to produce the new program will
be brittle and probably not well suited to that domain, since most of the
recognized phrases stem from a single (CF-producing) dialgoue.

While all the BEINGs' interactions were invisible to the user, the system still
swamped him with data 
about what was going on. Often, a single message would
issue simultaneously from several BEINGs (in slightly altered formats). The 
converse problem existed as well: it was necessary to include a BEING which
simulated forgetfulness, to prevent, e.g., delayed anaphora.   
Orienting the user was not solved satisfactorally. Pointers into
a graph of generated code were simulated, but often one wished to refer to
a piece of code not by name or by pointing, but by some brief meaningful
(to him only!) phrase.

The problem of locating relevant information is distributed
by giving each BEING the
responsibility for recognizing when it is talked about. This beats the
combinatorial nature of the problem on -- but ⊗4only⊗* on -- a computer with as
many processors as there are BEINGs.

Some of the difficulties stem from the nature of the task. In any long dialogue,
the user often forgets, changes his mind, errs, etc. A very sophistocated user
model would be necessary to accomodate this errorful process in a
non-debugging system. 
Without such abilities, the system itself may be led into error.
While most bugs ⊗4are⊗* avoidable by careful
record-keeping, it was unrealistic to make no provision for debugging a
new thirty-page program. When a few errors did occur, PUP6 itself had
to be altered.  The need for flexible dialogues was underestimated in this
domain.

The overall performance of BEINGs in PUP6 is mixed.
Two advantages were hoped for by using a uniform set of BEING parts.
Addition of new BEINGs to the pool was not easy (for untrained users)
but communication among
BEINGs ⊗4was⊗* easy (fast, natural). Two
advantages were hoped for by keeping the BEINGs highly structured.
The interactions (especially with the user) were
brittle, but
the complex tasks put to them ⊗4were⊗* completed.

The major problems are seen to be with user-system communication,
not with the BEINGs themselves. The ideas seem to fit together viably, and the
automatic programming itself went effortlessly.
Sophistocated, bug-free programs were generated, after hours of fairly high
level dialgue with an active user and tens of thousands of messages passed
among the BEINGs.

All this suggests two possible continuations. One is to 
rethink the communication problems,
and develop a better system for the
concept formation program generation task. This is now under study here at
the Stanford AI Lab.
The other continuation is to find a domain where
flexible natural language handling is not crucial. The author is currently
investigating elementary number theory as a potential task domain.
BEINGs will be present in that system, for their organizational power,
but so will many simpler and more efficient
internal mechanisms for representing and manipulating knowledge.

.B

.E
.ONCE CENTER
⊗5↓_10. References_↓⊗*

.BEGIN  INDENT 0 

.SPACING 25 MILLS
.PREFACE 100 MILLS

[1] Green et al.,
⊗4Progress Report on Program-Understanding Systems⊗*, Memo AIM-240,
CS Report STAN-CS-74-444,Artificial Intelligence Laboratory,
Stanford University, August, 1974.

[2] Hempel, Carl G., ⊗4Fundamentals of Concept Formation in
Empirical Science⊗*, University of Chicago, Chicago, Illinois,
1952.

[3] Hewitt, Carl, ⊗4A Universal Modular ACTOR Formalism for
Artificial Intelligence⊗*, Third International Joint Conference on
Artificial Intelligence,
1973, pp. 235-245.

[4] Minsky, Marvin, ⊗4Frames⊗*, in ⊗4Psychology of Computer
Vision⊗*, 1974.

[5] Teitelman, Warren, ⊗4INTERLISP Reference
Manual⊗*, XEROX PARC, 1974.

[6] Winston, Patrick, ⊗4Learning Structural Descriptions
from Examples⊗*, Ph.D. thesis, Dept. of Electrical Engineering,
TR-76, Project MAC, TR-231,
MIT AI Lab,
September, 1970.

[7] Woods, W.A., and Makhoul, J., ⊗4Mechanical Inference Problems in
Continuous Speech Understanding⊗*, Third IJCAI, pp. 200-207.


The ideas and the system described use concepts from ACTORS, 
heterarchy, structured programming, assertional data bases,
flexible data types, pattern-directed invocation of procedural
knowledge, the paradigm of dialogue, studies on program specification,
QLISP, INTERLISP, LISP, English,... In particular, the author  
drew heavily from creative discussions with C. Green, R. Waldinger,
D. Shaw, and E. Sacerdoti.
.END